package STO_17_13;

import java.util.Arrays;

public class Solution {
	public int respace(String[] dictionary, String sentence) {
		int n = sentence.length();
		Trie root = new Trie();
		for (String word : dictionary) {
			root.insert(word);
		}
		int[] dp = new int[n + 1];
		Arrays.fill(dp, Integer.MAX_VALUE);
		dp[0] = 0;
		for (int i = 1; i <= n; i++) {
			dp[i] = dp[i - 1] + 1;
			Trie curPos = root;
			for (int j = i; j >= 1; j--) {
				int t = sentence.charAt(j - 1) - 'a';
				if (curPos.next[t] == null) {
					break;
				} else if (curPos.next[t].isEnd) {
					dp[i] = Math.min(dp[i], dp[j - 1]);
				}
				if (dp[i]==0) {
					break;
				}
				curPos=curPos.next[t];
			}
		}
		return dp[n];
	}
}
